The present invention relates to computers and, more particularly, to integrated-circuit design. A major objective of the present invention is to provide a method for improving the timing characteristics of an integrated-circuit design including a combination-logic module.
Much of modern progress is associated with the proliferation of computers, which has been made possible by advances in integrated-circuit manufacturing technology. These advances have provided integrated circuits with ever increasing densities of circuit elementsxe2x80x94providing, in turn, higher speeds and more functionality per integrated circuit.
Most integrated circuits comprise identifiable functional blocks. Many such functional blocks implement combination logic; in other words, the block has an output that has a present value that is a predetermined function of the present values of plural inputs to the block under steady-state conditions. xe2x80x9cUnder steady-state conditionsxe2x80x9d means that the inputs have been held at constant values long enough that the output will not change except in response to a future change at the inputs. (An example of a non-combination-logic block is a counter, since its present output is dependent both on present and prior input values.)
In general, the time the effects of changes in input signals are evident in the output signals varies from input to input. There are three basic causes for this variance. The first source of variance is differing times of arrival of signal transitions at the inputs. Even in a synchronous system where all input changes are to occur within the same clock cycle, the transitions can occur at different phases within the clock cycle.
A second source of variance is xe2x80x9cfan-outxe2x80x9d. A large fan-out signal is one that drives many devices at once, and thus tends to make transitions more slowly than do small-fanout signals, which drive fewer devices. Thus, even if two transitions begin at the same time, the transition driving more devices takes longer to complete its transition. Accordingly, the effect of the slower transition appears later in the output.
The third source of variance is differences in latencies between respective inputs and the output. For example, different signals may have to traverse different numbers of gates; each gate can impose a delay that contributes to the latency.
The variance is a concern since it places a lower bound on the length of a clock cycle. A transition in the signal that is reflected most slowly must be reflected in the output before a subsequent transition in the signal that is reflected most quickly in the next cycle is reflected in the output. Therefore, successive changes in the block inputs must be separated in time by more than the variance in time inputs are reflected in the outputs. Therefore, the clock rate must be correspondingly limited and overall circuit performance limited.
Reducing the variance can thus improve performance. It is sometimes possible to design a block so that inputs associated with late-arriving signals (LAS) also have the shorter latencies so that the effects on output timing offset each other. In this case, the effects in the output of changes in the various inputs appear at nearer in time, facilitating fast, reliable reads.
To shorten design cycles, complex integrated circuits are typically designed by assembling modules selected from functional libraries of modules. Thus, a combination-logic function can be implemented by simply selecting an appropriate module rather than by designing a block from the transistor level. Since the modules in a library are to apply in a variety of contexts, they are typically designed without any advanced knowledge of any difference in the arrival times of input signals. Accordingly, the tendency is to design modules in which the latencies are relatively uniform across the inputs.
Once a module is incorporated into an actual integrated-circuit design, it may be found that the effects on the output of input transitions various from input-to-input to an unsatisfactory or undesirable degree. It is sometimes possible to find a more suitable module for the same function in the module library. Otherwise, it may be necessary to make ad hoc changes to the design or to redesign the functional block from scratch to meet requirements or otherwise optimize the design.
Certain types of modifications to modules have been taught for very specific design situations. For examples, some module libraries contain specific instructions for modifying a module to accommodate certain timing situations, for example, see HDL Synthesis: Synthesis Application Note, Synopsys, Inc., August, 1996, Chapter 2, pp. 11-27. However, the scope of such modifications is very narrow.
What is needed is a computer-implemented method for redesigning combination-logic modules to accommodate different signal arrival times at different inputs and thus to improve the timing characteristics of the incorporating integrated circuit. Such a method would improve the competitiveness of modularly designed integrated circuits, on the one hand, and reduce the effort required to achieve high-performance integrated circuits on the other.
The present invention provides a computer-implemented method for potentially improving the timing characteristics of an integrated circuit design including a combination-logic module. A last signal, e.g., the signal most belatedly reflected in the out put of the original combination-logic module, is identified. The original module is converted to a second module that has two logic submodules and an output multiplexer. One submodule provides the same result as the original module when the last signal is high, while the other provides the same result as the original module when the last signal is low. The last signal is not input to the submodules, but serves as the control signal for the multiplexer so that the revised module implements the same logic function as the original module.
The timing of the last signal is, in general, advanced by moving it from its position as a logic input in the original module to its position as an output multiplexer control signal in the second module. If the timing of the last signal is still not adequate, it is unlikely that the timing specification can be met. However, if the timing of the last signal is adequate, other signals with problematic timing can be addressed by iterating the method.
The combination-logic submodules are readily derived from the original module by applying constant signals to the inputs that formerly received the last input signal. In one submodule, all inputs formerly associated with the last input are held high; in the other submodule the corresponding inputs are held low. In many cases, further improvements in the submodule designs can be effected using more sophisticated design algorithms and/or taking advantage of operator intervention.
Because the last input is not a factor within the submodules, their latencies can be less than the latency for the original module. However, the additional latency due to the multiplexer might cause some latencies across the module to increase. Accordingly, it is generally desirable to test the redesigned module to determine whether a specification has been met or whether an improvement has actually been effected.
The invention provides for a two-pronged testing of revised modules. The first issue is whether the revised module meets predetermined timing specifications. If it does, the method provides for implementing the revised module. Alternatively, the method can be iterated to determine if further improvements to timing might be available.
If the specifications are not met, the second issue arises: is the failure due to the timing of the last signal or another signal. If it is due to the last signal, further iterations of the method are not likely to result in improvements; accordingly, the method can be terminated. If the failure is not due to the last input, further improvements may be achieved by additional iterations of the method.
The Nth iteration of the method involves determining an Nth last signal. The Nth last signal is preferably determined at a respective Nth iteration of the method. It is not necessarily the Nth last signal as determined on the first iteration.
For every iteration of the method beyond the first, there is already an output multiplexer. The Nth last signal, where N greater than 1, becomes a multiplexer control along with previous last signals, and the number of combination-logic submodules doubles. (In some cases, some submodules prove to be degenerate and need not be represented in the revised module.)
For the second and succeeding iterations, there is an option to have the Nth last signal control a new multiplexer stage or share control of a stage previously controlled, at least in part, by the (Nxe2x88x921)st last signal. In a preferred realization, both are tried and testedxe2x80x94with the better one being implemented if they both pass.
In another preferred realization, the Nth last signal is added to the first pre-existing multiplexer stage. If this module fails due to a prior last signal""s lateness, it can be assumed that the additional complexity of the first stage causes a prior last signal controlling the first stage to fall below specification. Accordingly, a new stage can added to the multiplexer to be controlled by the Nth last signal. This restores the prior last signal to a situation in which its timing was previously found satisfactory. On the other hand, the present late signal must traverse an extra multiplexer stage. Accordingly, the timing of the present late signal might fail even though it was satisfactory before the new stage was added. However, if it fails, the method is stopped because it is already determined that controlling a subsequent stage with the present late signal would not yield satisfactory results.
If the method is taken to its extreme conclusion, the result is a look-up table having the module inputs as address lines, and the entries the precalculated results of logic operations. In practice, the method would be terminated well before this result. Accordingly, the invention provides for setting an iteration threshold T that corresponds to the number of module inputs that will remain as submodule inputs (and not multiplexer inputs) after an iteration is complete. T can be selected so that 0xe2x89xa6T less than P, where P is the number of module inputs. The method provides for halting the iterations when the number N of iterations is greater than Pxe2x88x92T. Preferably, T is at least one-half P.
The invention provides for different methods of determining lateness. The parameter of greatest interest is generally the relative time a change in a logic input signal is appropriately reflected in the logic output. In general, the most important factor for a standard logic module is the time of arrival of the inputs from upstream components of the incorporating integrated circuit. However, input fan-out and latency across the module can also be included in the determination of lateness.